package cn.mayday.algorithms.year2021.month1.C双指针专题;

/**
 * @description: 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 * @author: mayday
 * @date: 2020/9/6 23:53
 * @version: 1.0
 */
public class Arrow21Exchange {

    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4};


    }

    /**
     * 双指针实现
     * left从左边开始扫描，如果是奇数就往右走，如果遇到偶数就停下来（此时left指向的是偶数），
     * right从右边开始扫描，如果是偶数就往左走，如果是奇数就停下来（此时right指向的是奇数），
     * 交换left和right指向的值。
     *

     * @param nums
     * @return
     */
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        while (leftIndex < rightIndex) {
            // 从左，如果为奇数继续右移
            while (leftIndex < rightIndex && (nums[leftIndex] & 1) == 1) {
                leftIndex++;
            }

            // 从右，如果为偶数继续右移
            while (leftIndex < rightIndex && (nums[rightIndex] & 1) == 0) {
                rightIndex--;
            }

            // 同时找到合适的奇数和偶数位置，互换
            if (leftIndex < rightIndex) {
                int temp = nums[leftIndex];
                nums[leftIndex] = nums[rightIndex];
                nums[rightIndex] = temp;
            }
        }
        return nums;
    }
}
